package sort;

public class QuickSort {
	
	public void quickSort(int arr[],int n){
		this.quickSort(arr,0,n-1);
	}
	
	private void quickSort(int arr[],int l,int r){
		if(l >= r)
			return;
		
		int p = partition(arr,l,r);
		this.quickSort(arr,l,p-1);
		this.quickSort(arr,p+1,r);
	}
	
	private int partition(int arr[],int l,int r){
		int v = arr[l];
		
		int j = l;
		for( int i = l + 1; i <= r ; i ++ ){
			if(arr[i] < v){
				this.swap(arr,++j,i);
			}
		}
		this.swap(arr, l, j);
		return j;
	}
	
	private void swap(int[] arr,int i,int j){
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
	
	public static void main(String[] args) {
		int[] arr = new int[]{2,41,1,1,5,35,26,34,2,34};
		new QuickSort().quickSort(arr, arr.length);
		for(int a : arr){
			System.out.println(a);
		}
	}
}
